// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ssa

import (
	"fmt"
	"strings"
)

type SparseTreeNode struct {
	child   *Block
	sibling *Block
	parent  *Block

	// 每个街区都有6个与之关联的数字：
	// 入口1，入口+1，出口-1，出口+1。
	// 入口和出口在概念上是块的顶部（phi函数）
	// 入口+1和出口-1在概念上是块的底部（普通DEF）
	// 入口-1和出口+1在概念上是块的“正前方”（流入的条件）
	// 
	// 如果我们想查询关于x的信息，这简化了生活
	// 当x既是块的输入又是块的输出时。
	entry, exit int32
}

func (s *SparseTreeNode) String() string {
	return fmt.Sprintf("[%d,%d]", s.entry, s.exit)
}

func (s *SparseTreeNode) Entry() int32 {
	return s.entry
}

func (s *SparseTreeNode) Exit() int32 {
	return s.exit
}

const (
	// 用于在稀疏树中查找定义时，
	// 对块的输入（+adjust）和
	// 退出（-adjust）数字的这些调整允许在“块”之前（例如，作为块及其phi函数的输入
	// 条件）之间进行区分，
	// 在“块”内”发生的赋值（通常是分支相关的
	// 和“之后”块。
	AdjustBefore = -1 // 在phi之前定义
	AdjustWithin = 0  // 在phi之前定义
	AdjustAfter  = 1  // 在块
)

// 稀疏树是块树。
// 它允许快速的祖先查询，
// 例如一个块是否支配另一个块。
type SparseTree []SparseTreeNode

// newSparseTree从块到父映射（按block.ID索引的数组）创建一个SparseTree（按block.ID索引）
func newSparseTree(f *Func, parentOf []*Block) SparseTree {
	t := make(SparseTree, f.NumBlocks())
	for _, b := range f.Blocks {
		n := &t[b.ID]
		if p := parentOf[b.ID]; p != nil {
			n.parent = p
			n.sibling = t[p.ID].child
			t[p.ID].child = b
		}
	}
	t.numberBlock(f.Entry, 1)
	return t
}

// newSparseOrderedTree从块到父映射（按block.ID索引的数组）创建一个SparseTree（按block.ID索引的数组）
// 子级将以相反的顺序出现在reverseOrder 
// 特别是，如果reverseOrder是dfs ReverseStorder，然后根给孩子们
// 走树会产生一个预订单。
func newSparseOrderedTree(f *Func, parentOf, reverseOrder []*Block) SparseTree {
	t := make(SparseTree, f.NumBlocks())
	for _, b := range reverseOrder {
		n := &t[b.ID]
		if p := parentOf[b.ID]; p != nil {
			n.parent = p
			n.sibling = t[p.ID].child
			t[p.ID].child = b
		}
	}
	t.numberBlock(f.Entry, 1)
	return t
}

// treestructure提供了控制程序
// 块b及其控制的所有块的树和流结构的字符串描述。
func (t SparseTree) treestructure(b *Block) string {
	return t.treestructure1(b, 0)
}
func (t SparseTree) treestructure1(b *Block, i int) string {
	s := "\n" + strings.Repeat("\t", i) + b.String() + "->["
	for i, e := range b.Succs {
		if i > 0 {
			s += ","
		}
		s += e.b.String()
	}
	s += "]"
	if c0 := t[b.ID].child; c0 != nil {
		s += "("
		for c := c0; c != nil; c = t[c.ID].sibling {
			if c != c0 {
				s += " "
			}
			s += t.treestructure1(c, i+1)
		}
		s += ")"
	}
	return s
}

// numberBlock为b和b的
// 按顺序行走的儿童分配入口和出口号码，其中n 
// 是尚未分配或保留的第一个号码。N应该
// 大于零。对于每个出入境号码，
// 保留一个大一个小的值，以表示
// “严格高于”和“严格低于”。numberBlock返回
// 尚未分配或保留的最小数字（即
// 最后访问的块的出口号，加上两个，因为
// 最后。出口+1是保留值。）
// 
// 示例：
// 
// 单节点树根，n=1调用
// 入口=2根出口=5；返回7 
// 
// 两节点树，根->子节点，调用n=1 
// entry=2 Root exit=11；返回13 
// entry=5 Child exit=8 
// 
// 三节点树，根->（左，右），调用n=1 
// entry=2根出口=17；返回19 
// entry=5 Left exit=8；entry=11 Right exit=14 
// 
// 这是分配和保留的数字的顺序
// 最后一个例子：
// 根左右根
// 1 2e 3 | 4 5e 6 | 7 8x 9 | 10 11e 12 | 13 14x 15 | 16 17x 18 

func (t SparseTree) numberBlock(b *Block, n int32) int32 {
	n++
	t[b.ID].entry = n
	// 将n+1保留给条目
	n += 2
	for c := t[b.ID].child; c != nil; c = t[c.ID].sibling {
		n = t.numberBlock(c, n) // 保留n=下一个自由数
	}
	// 将n保留给出口-1，将n+1分配给出口
	n++
	t[b.ID].exit = n
	// 将n+1保留给出口+1，n+2是下一个自由数，返回。
	return n + 2
}

// Sibling返回支配器树中x的同级（即，
// 具有相同直接支配器的节点），如果在任意但可重复的
// 顺序中没有剩余同级，则返回nil。由于子兄弟顺序用于分配树状通道中的入口和出口编号，这些编号也与此顺序一致（即，
// 兄弟（x）的入口编号大于x的出口编号）。
func (t SparseTree) Sibling(x *Block) *Block {
	return t[x.ID].sibling
}

// Child在支配树中返回x的子级，如果没有，则返回
// nil。第一个孩子的选择是随意的，但可以重复。
func (t SparseTree) Child(x *Block) *Block {
	return t[x.ID].child
}

// Parent返回支配树中x的父级，如果x是函数的条目，则返回
// nil。
func (t SparseTree) Parent(x *Block) *Block {
	return t[x.ID].parent
}

// isAncestorEq报告x是否是y的祖先或等于y。
func (t SparseTree) IsAncestorEq(x, y *Block) bool {
	if x == y {
		return true
	}
	xx := &t[x.ID]
	yy := &t[y.ID]
	return xx.entry <= yy.entry && yy.exit <= xx.exit
}

// isAncestor报告x是否是y的严格祖先。
func (t SparseTree) isAncestor(x, y *Block) bool {
	if x == y {
		return false
	}
	xx := &t[x.ID]
	yy := &t[y.ID]
	return xx.entry < yy.entry && yy.exit < xx.exit
}

// domorder返回一个值，用于面向支配者的排序。
// 块控制不提供总排序，
// 但DOMDORDER 2具有有用的属性。如果domorder（x）>domorder（y），那么x不支配y。如果domorder（x）<domorder（y）和domorder（y）<domorder（z），并且x不支配y，那么x不支配z。属性（1）意味着按domorder排序的块总是首先有一个最大支配块。
// 属性（2）允许搜索主导区块提前退出。
func (t SparseTree) domorder(x *Block) int32 {
	// 这里有一个参数，即条目（x）提供了上面记录的属性。
	// 
	// 在深度优先的支配树漫游中分配入口和出口值。
	// 对于所有区块x和y，其中一种观点认为：
	// 
	// （x-dom-y）x支配y=>entry（x）<entry（y）<exit（y）<exit（y）<exit（y）
	// （y-dom-x）y支配x=>entry（y）<entry（x）<exit（y）
	// 
	// entry（x）>entry（y）消除了情况x-dom-y。这提供了上述属性（1）。对于属性（2），假设条目（x）<条目（y）和条目（y）<条目（z）和x不支配y。条目（x）<条目（y）允许x-dom-y和x-then-y。但是通过假设，x不支配y。所以我们有x-then-y。条目（x）<条目（y）允许x-dom-y和x-then-y，假设x支配z。
	// 然后进入（x）<进入（z）<退出（z）<退出（x）。但是我们知道x-then-y，所以进入（x）<退出（x）<进入（y）<退出（y）。
	// 结合这些，入口（x）<入口（z）<出口（z）<出口（x）<入口（y）<出口（y）。
	// 通过假设，entry（y）<entry（z），它允许y-dom-z和y-then-z的情况。
	// y-dom-z需要entry（y）<entry（z），但我们有entry（z）<entry（y）。
	// y-then-z要求退出（y）<进入（z），但我们有进入（z）<退出（y）。
	// 我们有一个矛盾，所以x不能按要求控制z。
	return t[x.ID].entry
}
